package tree

func QuickSort(nums []int) []int {
	// 把一个数组分为左右两段，左段<右段，类似分治法，无合并过程
	quickSort(nums, 0, len(nums)-1)
	return nums
}

func quickSort(nums []int, start, end int) {
	if start < end {
		//divide
		pivot := partition(nums, start, end)
		quickSort(nums, 0, pivot-1)
		quickSort(nums, pivot+1, end)
		//因为是原地交换，所以没有合并的过程
	}
}

func partition(nums []int, start, end int) int {
	p := nums[end]
	i := start
	for j := start; j < end; j++ {
		if nums[j] < p { // i的值都是<p的
			swap(nums, i, j)
			i++
		}
	}
	//把中间的值换为用于比较的基准值
	swap(nums, i, end)
	return i
}

func swap(nums []int, i, j int) {
	t := nums[i]
	nums[i] = nums[j]
	nums[j] = t
}
